#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
Miguel Silva, 6311
Estrutura de Dados e Algoritmos
Engenharia Informática 
2012/2013
"""

class HeapsortClass(object):
	"""
	Classe utilizada para representação do algoritmo de 
	ordenação Heapsort
	"""
	def __init__(self):
		"""
		Constructor da classe HeapsortClass
		"""
		super(HeapsortClass, self).__init__()
		self.size = 0

	def heapsort(self,list):
		"""
		Função que constroi a lista, satisfazendo a propriedade max-heap,
		e ordena a lista de forma crescente.

		Argumentos:
		list -- lista
		"""
		self.build_max_heap(list)
		for index in range((self.size), 0, -1):
			list[0], list[index] = list[index], list[0]
			self.size = self.size-1
			self.max_heapify(list,0)

	def max_heapify(self,list,index):
		"""
		Função que assegura a propriedade heap, ou seja,
		que o nó pai é sempre maior que os nós filhos.

		Argumentos:
		list -- lista
		index -- indice
		"""

		l = self.left(index)
		r = self.right(index)

		if l <= self.size and list[l] > list[index]:
			largest = l

		else:
			largest = index

		if r <= self.size and list[r] > list[largest]:
			largest = r

		if largest != index:
			list[index],list[largest] = list[largest], list[index]
			self.max_heapify(list, largest)

	def build_max_heap(self,list):
		"""
		Função que garante que o maior valor da listas se encontra
		no topo da arvore.

		Argumentos:
		list -- lista
		"""
		self.size = len(list)-1
		half_size = self.size/2
		for index in range((half_size),0,-1):		
			self.max_heapify(list,index)

	def parent(self, index):
		"""
		Função que calcula o nó pai de acordo com o index
		recebido por parâmetro.

		Argumentos:
		index -- indice

		Return:
		O resultado da operação index/2
		"""
		return index/2

	def right(self,index):
		"""
		Função que calcula o nó filho da direita de acordo
		com o index recebido por parâmetro.

		Argumentos:
		index -- indice

		Return:
		O resultado da operação 2*index+2
		"""
		return 2*index+2

	def left(self, index):
		"""
		Função que calcula o nó filho da esquerda de acordo
		com o index recebido por parâmetro.

		Argumentos:
		index -- indice

		Return:
		O resultado da operação 2*index+1
		"""
		return 2*index+1